package algorithm;

/**
 * Created with IntelliJ IDEA.
 * User: Kvest
 * Date: 31.08.13
 * Time: 13:33
 * To change this template use File | Settings | File Templates.
 */
public class UF {
    private int[] id;
    private int[] weights;
    private int count;

    public UF(int size) {
        id = new int[size];
        weights = new int[size];
        for (int i = 0; i < size; ++i) {
            id[i] = i;
            weights[i] = 0;
        }
        count = size;
    }

    public void union(int p, int q) {
        p = find(p);
        q = find(q);
        if (p == q) {
            return;
        }

        if (weights[p] > weights[q]) {
            weights[p] += weights[q];
            id[q] = p;
        } else {
            weights[q] += weights[p];
            id[p] = q;
        }
        --count;
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    public int count() {
        return count;
    }

    private int find(int p) {
        while (p != id[p]) {
            p = id[p];
        }
        return p;
    }

    public static void test() {
        UF uf = new UF(10);
        System.out.println("count[10]=" + uf.count());
        System.out.println("1 with 9[false]=" + uf.connected(1,9));
        System.out.println("0 with 9[false]=" + uf.connected(0,9));
        System.out.println("5 with 6[false]=" + uf.connected(5,6));
        System.out.println("8 with 2[false]=" + uf.connected(8,2));
        System.out.println("7 with 7[true]=" + uf.connected(7,7));

        uf.union(0,5);
        uf.union(5,6);
        uf.union(2,7);
        uf.union(4,7);
        uf.union(9,4);
        uf.union(2,1);
        uf.union(1,7);
        System.out.println("count[4]=" + uf.count());
        System.out.println("5 with 2[false]=" + uf.connected(5,2));
        System.out.println("6 with 3[false]=" + uf.connected(6,3));
        System.out.println("3 with 1[false]=" + uf.connected(3,1));
        System.out.println("8 with 7[false]=" + uf.connected(8,7));

        System.out.println("5 with 6[true]=" + uf.connected(5,6));
        System.out.println("6 with 0[true]=" + uf.connected(6,0));
        System.out.println("1 with 2[true]=" + uf.connected(1,2));
        System.out.println("2 with 9[true]=" + uf.connected(2,9));
        System.out.println("1 with 9[true]=" + uf.connected(1,9));

        uf.union(3,8);
        uf.union(3,5);
        System.out.println("count[2]=" + uf.count());
        System.out.println("8 with 5[true]=" + uf.connected(8,5));
        System.out.println("6 with 3[true]=" + uf.connected(6,3));
        System.out.println("3 with 1[false]=" + uf.connected(3,1));
        System.out.println("8 with 7[false]=" + uf.connected(8,7));

        uf.union(3,9);
        System.out.println("count[1]=" + uf.count());
        System.out.println("5 with 2[true]=" + uf.connected(5,2));
        System.out.println("6 with 3[true]=" + uf.connected(6,3));
        System.out.println("3 with 1[true]=" + uf.connected(3,1));
        System.out.println("8 with 7[true]=" + uf.connected(8,7));
        System.out.println("5 with 6[true]=" + uf.connected(5,6));
        System.out.println("6 with 0[true]=" + uf.connected(6,0));
        System.out.println("1 with 2[true]=" + uf.connected(1,2));
        System.out.println("2 with 9[true]=" + uf.connected(2,9));
        System.out.println("1 with 9[true]=" + uf.connected(1,9));
    }
}
